πŸ‘©β€πŸ’» 43165. νƒ€κ²Ÿ λ„˜λ²„

@Seongukbaek Posted April 11, 2022 Β· Updated April 11, 2022 Β· 3 min read

문제

n개의 음이 μ•„λ‹Œ μ •μˆ˜λ“€μ΄ μžˆμŠ΅λ‹ˆλ‹€. 이 μ •μˆ˜λ“€μ„ μˆœμ„œλ₯Ό λ°”κΎΈμ§€ μ•Šκ³  적절히 λ”ν•˜κ±°λ‚˜ λΉΌμ„œ νƒ€κ²Ÿ λ„˜λ²„λ₯Ό λ§Œλ“€λ €κ³  ν•©λ‹ˆλ‹€. 예λ₯Ό λ“€μ–΄ [1, 1, 1, 1, 1]둜 숫자 3을 λ§Œλ“€λ €λ©΄ λ‹€μŒ λ‹€μ„― 방법을 μ“Έ 수 μžˆμŠ΅λ‹ˆλ‹€.

-1+1+1+1+1 = 3 +1-1+1+1+1 = 3 +1+1-1+1+1 = 3 +1+1+1-1+1 = 3 +1+1+1+1-1 = 3

μ‚¬μš©ν•  수 μžˆλŠ” μˆ«μžκ°€ λ‹΄κΈ΄ λ°°μ—΄ numbers, νƒ€κ²Ÿ λ„˜λ²„ target이 λ§€κ°œλ³€μˆ˜λ‘œ μ£Όμ–΄μ§ˆ λ•Œ 숫자λ₯Ό 적절히 λ”ν•˜κ³  λΉΌμ„œ νƒ€κ²Ÿ λ„˜λ²„λ₯Ό λ§Œλ“œλŠ” λ°©λ²•μ˜ 수λ₯Ό return ν•˜λ„λ‘ solution ν•¨μˆ˜λ₯Ό μž‘μ„±ν•΄μ£Όμ„Έμš”.

μ œν•œμ‚¬ν•­

  • μ£Όμ–΄μ§€λŠ” 숫자의 κ°œμˆ˜λŠ” 2개 이상 20개 μ΄ν•˜μž…λ‹ˆλ‹€.
  • 각 μˆ«μžλŠ” 1 이상 50 μ΄ν•˜μΈ μžμ—°μˆ˜μž…λ‹ˆλ‹€.
  • νƒ€κ²Ÿ λ„˜λ²„λŠ” 1 이상 1000 μ΄ν•˜μΈ μžμ—°μˆ˜μž…λ‹ˆλ‹€.

μž…μΆœλ ₯ 예

numbers target return
[1, 1, 1, 1, 1] 3 5
[4, 1, 2, 1] 4 2

πŸ“ Logic

private void dfs(int[] numbers, int idx, int target, int sum) { if (idx + 1 == numbers.length) { if (sum == target) answer++; return; } dfs(numbers, idx + 1, target, sum + numbers[idx + 1]); dfs(numbers, idx + 1, target, sum - numbers[idx + 1]); }
  • μž¬κ·€μ μΈ DFSλ₯Ό μ΄μš©ν•΄ λ‹€μŒ numberλ₯Ό λ”ν•˜κ±°λ‚˜ λΉΌλ©΄μ„œ 맨 λ§ˆμ§€λ§‰ 값이 νƒ€κ²Ÿ λ„˜λ²„μ™€ 같은 경우 answerλ₯Ό μ¦κ°€ν•œλ‹€.
  • 첫 번째 μˆ«μžκ°€ μ–‘μˆ˜μΈ κ²½μš°μ™€ 음수인 경우 두 가지에 λŒ€ν•΄ dfsλ₯Ό ν˜ΈμΆœν•œλ‹€.

πŸ“„ CODE

μ½”λ“œ 보기/μ ‘κΈ°πŸ’«
import java.util.*; class Solution { static int answer = 0; public int solution(int[] numbers, int target) { dfs(numbers, 0, target, numbers[0]); return answer; } private void dfs(int[] numbers, int idx, int target, int sum) { if (idx + 1 == numbers.length) { if (sum == target) answer++; return; } dfs(numbers, idx + 1, target, sum + numbers[idx + 1]); dfs(numbers, idx + 1, target, sum - numbers[idx + 1]); } }

✏️ Review

  • μ²˜μŒμ—λŠ” 트리λ₯Ό λ§Œλ“€μ–΄μ„œ 맨 λ§ˆμ§€λ§‰ 리프 λ…Έλ“œκ°€ νƒ€κ²Ÿ λ„˜λ²„λž‘ 같은 경우의 수λ₯Ό μ²΄ν¬ν•΄μ•Όν•˜λ‚˜ μƒκ°ν–ˆλ‹€.
  • 이전에 DFS 문제λ₯Ό ν’€ λ•Œ λ­”κ°€ μž¬κ·€ ν˜ΈμΆœμ„ μ΄μš©ν•œ DFS둜 λΉ„μŠ·ν•œ 문제λ₯Ό ν’€μ—ˆλ˜ 것이 μƒκ°λ‚˜ κ΅¬ν˜„ν•΄λ³΄λ‹ˆ μ •λ‹΅μ΄μ—ˆλ‹€.
  • 쓸데없이 트리λ₯Ό κ΅¬ν˜„ν•  λ»” ν–ˆλ‹€.

πŸ“• 좜처

Programmers : https://programmers.co.kr/learn/courses/30/lessons/43165

@Seongukbaek
배우고 μ •λ¦¬ν•˜κ³  κ³΅μœ ν•˜λŠ” λŒ€ν•™μƒ λ°±μ„±μš±μž…λ‹ˆλ‹€ πŸ˜€